<?php
/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: SortedMap.php 14 2006-11-28 22:05:19Z rdff3 $
 */
/**
 *
 */
require_once( "lang/Object.php" );
require_once( "util/Collection.php" );

/** 
 * SortedMap
 * 
 * A map that further guarantees that it will be in ascending key order, sorted according to the natural ordering of its keys 
 * (see the Comparable interface), or by a comparator provided at sorted map creation time. This order is reflected when iterating 
 * over the sorted map's collection views (returned by the entrySet, keySet  and values methods). Several additional operations 
 * are provided to take advantage of the ordering. (This interface is the map analogue of the SortedSet interface.)
 * 
 * All keys inserted into a sorted map must implement the Comparable interface (or be accepted by the specified comparator). 
 * Furthermore, all such keys must be mutually comparable: k1.compareTo(k2) (or comparator.compare(k1, k2)) must not throw a 
 * ClassCastException for any elements k1 and k2 in the sorted map. Attempts to violate this restriction will cause the offending 
 * method or constructor invocation to throw a ClassCastException.
 * 
 * Note that the ordering maintained by a sorted map (whether or not an explicit comparator is provided) must be consistent with 
 * equals if the sorted map is to correctly implement the Map interface. (See the Comparable interface or Comparator interface for 
 * a precise definition of consistent with equals.) This is so because the Map interface is defined in terms of the equals operation, 
 * but a sorted map performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this
 * method are, from the standpoint of the sorted map, equal. The behavior of a tree map is well-defined even if its ordering is 
 * inconsistent with equals; it just fails to obey the general contract of the Map interface.
 * 
 * All general-purpose sorted map implementation classes should provide four "standard" constructors: 1) A void (no arguments)
 * constructor, which creates an empty sorted map sorted according to the natural order of its keys. 2) A constructor with a 
 * single argument of type Comparator, which creates an empty sorted map sorted according to the specified comparator. 3) A 
 * constructor with a single argument of type Map, which creates a new map with the same key-value mappings as its argument, 
 * sorted according to the keys' natural ordering. 4) A constructor with a single argument of type sorted map, which creates a new 
 * sorted map with the same key-value mappings and the same ordering as the input sorted map. There is no way to enforce this 
 * recommendation (as interfaces cannot contain constructors) but the JDK implementation (TreeMap) complies.
 * 
 * This interface is a member of the PHP Collections Framework. 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: SortedMap.php 14 2006-11-28 22:05:19Z rdff3 $
 */
interface SortedMap extends Map {
	/**
	 * Returns the comparator associated with this sorted set, or null if it uses its elements' natural ordering.
	 *
	 * @returns Comparator the comparator associated with this sorted set, or null if it uses its elements' natural ordering.
	 */
	public function comparator();
	
	/**
	 * Returns the first (lowest) key currently in this sorted map.
	 *
	 * @return Object the first (lowest) key currently in this sorted map.
	 * @throws NoSuchElementException - if this map is empty.
	 */
	public function firstKey();
	
	/**
	 * Returns a view of the portion of this sorted map whose keys are strictly less than toKey.
	 *
	 * Returns a view of the portion of this sorted map whose keys are strictly less than toKey. The returned sorted map is backed 
	 * by this sorted map, so changes in the returned sorted map are reflected in this sorted map, and vice-versa. The returned map
	 * supports all optional map operations that this sorted map supports.
	 * 
	 * The map returned by this method will throw an IllegalArgumentException if the user attempts to insert a key outside the 
	 * specified range.
	 * 
	 * Note: this method always returns a view that does not contain its (high) endpoint. If you need a view that does contain 
	 * this endpoint, and the key type allows for calculation of the successor a given key, merely request a headMap bounded by 
	 * successor(highEndpoint). For example, suppose that suppose that m is a map whose keys are strings. The following idiom obtains 
	 * a view containing all of the key-value mappings in m whose keys are less than or equal to high:
	 * 
	 *     Map head = m.headMap(high+"\0");
	 *
	 * @param Comparable $toKey high endpoint (exclusive) of the subMap.
	 * @returns SortedSet a view of the specified initial range of this sorted map.
	 *
	 * @throws {@link ClassCastException} - if toKey is not compatible with this map's comparator (or, if the map has no 
	 * 		comparator, if toKey does not implement Comparable). Implementations may, but are not required to, throw this exception if 
	 * 		toKey cannot be compared to keys currently in the map.
	 * @throws {@link NullPointerException} - if toKey is null and this sorted map does not tolerate null keys.
	 * @throws {@link IllegalArgumentException} -if this map is itself a subMap, headMap, or tailMap, and toKey is not within 
	 * 		the specified range of the subMap, headMap, or tailMap.
	 */
	public function headMap( Object $toKey );
	
	/** 
	 * Returns the last (highest) element currently in this sorted map.
	 *
	 * @return Object the last (highest) element currently in this sorted map.
	 * @throws NoSuchElementException - if this map is empty.
	 */
	public function lastKey();
	
	/**
	 * Returns a view of the portion of this sorted map whose keys range from fromKey, inclusive, to toKey, exclusive.
	 * 
	 * Returns a view of the portion of this sorted map whose keys range from fromKey, inclusive, to toKey, exclusive. (If fromKey 
	 * and toKey are equal, the returned sorted map is empty.) The returned sorted map is backed by this sorted map, so changes in 
	 * the returned sorted map are reflected in this sorted map, and vice-versa. The returned Map supports all optional map 
	 * operations that this sorted map supports.
	 * 
	 * The map returned by this method will throw an IllegalArgumentException if the user attempts to insert a key outside the 
	 * specified range.
	 * 
	 * Note: this method always returns a half-open range (which includes its low endpoint but not its high endpoint). If you 
	 * need a closed range (which includes both endpoints), and the key type allows for calculation of the successor a given key, 
	 * merely request the subrange from lowEndpoint to successor(highEndpoint). For example, suppose that m is a map whose keys are 
	 * strings. The following idiom obtains a view containing all of the key-value mappings in m whose keys are between low and high, 
	 * inclusive:
	 * 
	 * 		Map sub = m.subMap(low, high+"\0");
	 * 
	 * A similarly technique can be used to generate an open range (which contains neither endpoint). The following idiom obtains a 
	 * view containing all of the key-value mappings in m whose keys are between low and high, exclusive:
	 * 
	 *     Map sub = m.subMap(low+"\0", high);
	 * 
	 * @param Comparable $fromKey - low endpoint (inclusive) of the subMap.
	 * @param Comparable $toKey - high endpoint (exclusive) of the subMap.
	 * @returns SortedMap a view of the specified range within this sorted map.
	 * 
	 * @throws {@link ClassCastException} - if fromKey and toKey  cannot be compared to one another using this map's comparator 
	 * 		(or, if the map has no comparator, using natural ordering). Implementations may, but are not required to, throw this 
	 * 		exception if fromKey or toKey  cannot be compared to keys currently in the map.
	 * @throws {@link IllegalArgumentException} - if fromKey is greater than toKey; or if this map is itself a subMap, headMap, 
	 * 		or tailMap, and fromKey or toKey are not within the specified range of the subMap, headMap, or tailMap.
	 * @throws {@link NullPointerException} - if fromKey or toKey is null and this sorted map does not tolerate null keys.
	 */
	public function subMap( Object $fromKey, Object $toKey );
	
	
	/**
	 * Returns a view of the portion of this sorted map whose keys are strictly greater than or equal to fromKey.
	 *
	 * Returns a view of the portion of this sorted map whose keys are greater than or equal to fromKey.  The returned sorted map 
	 * is backed by this sorted map, so changes in the returned sorted map are reflected in this sorted map, and vice-versa. The 
	 * returned map supports all optional map operations that this sorted map supports.
	 * 
	 * The map returned by this method will throw an IllegalArgumentException if the user attempts to insert a key outside the 
	 * specified range.
	 * 
	 * Note: this method always returns a view that does not contain its (high) endpoint. If you need a view that does contain 
	 * this endpoint, and the key type allows for calculation of the successor a given key, merely request a headMap bounded by 
	 * successor(lowEndpoint). For example, suppose that suppose that m is a map whose keys are strings. The following idiom obtains 
	 * a view containing all of the key-value mappings in m whose keys are greater than low:
	 * 
	 *     Map tail = m.tailMap(low+"\0");
	 *
	 * @param Comparable $fromKey lov endpoint (inclusive) of the subMap.
	 * @returns SortedMap a view of the specified initial range of this sorted map.
	 *
	 * @throws {@link ClassCastException} - if fromKey is not compatible with this map's comparator (or, if the map has no 
	 * 		comparator, if toKey does not implement Comparable). Implementations may, but are not required to, throw this exception if 
	 * 		fromKey cannot be compared to keys currently in the map.
	 * @throws {@link NullPointerException} - if fromKey is null and this sorted map does not tolerate null keys.
	 * @throws {@link IllegalArgumentException} -if this map is itself a subMap, headMap, or tailMap, and fromKey is not within 
	 * 		the specified range of the subMap, headMap, or tailMap.
	 */
	public function tailMap( Object $fromKey);
}



?>